package leetcode4;
import java.util.*;
public class test9 {
    /*
    * 前缀和
    * */
//    public int subarraySum(int[] nums, int k) {
//          int[] pre = new int[nums.length + 1];
//          for(int i = 0;i < nums.length;i++){
//              pre[i+1] = pre[i] + nums[i];
//          }
//          int count = 0;
//          for(int left = 0;left < nums.length;left++){
//              for(int right = left;right < nums.length;right++){
//                  if(pre[right + 1] - pre[left] == k){
//                      count++;
//                  }
//              }
//          }
//          return count;
//    }

    /*
    *
    * 前缀和+哈希表*/
    public int subarraySum(int[] nums, int k){
        Map<Integer,Integer> map = new HashMap<>();
        int count = 0;
        int preSum = 0;
        map.put(0,1);
        for(int num:nums){
            preSum += num;
            if(map.containsKey(preSum - k)){
                count += map.get(preSum - k);
            }
            map.put(preSum,map.getOrDefault(preSum,0) + 1);
        }
        return count;
    }
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int count = 0;
        int pre = 0;
        for(int num:nums){
            if(num % 2 == 1){
                pre++;
            }
            if(map.containsKey(pre - k)){
                count += map.get(pre - k);
            }
            map.put(pre,map.getOrDefault(pre,0) + 1);
        }
        return count;
    }

}
